//
//  Train. 批量建堆.swift
//  LeetCodeTrain
//
//  Created by rjb on 2021/6/3.
//  Copyright © 2021 rjb. All rights reserved.
//

import Foundation
// 批量建堆有两种做法
// 第一种：自上而下的上滤
// 第二种：自下而上的下滤（效率稍微高点）
// 这两种方法：想想看。
// 如果从前向后处理，后面的元素有可能需要上窜到前面；
// 如果从后想前处理，前面的元素可能需要下沉到后面；
class BinaryHeapHeapify {
    func heapify(a: inout [Int]) {
        // 如果从前向后处理，后面的元素有可能需要上窜到前面；
        for index in 0..<a.count {
            siftUp(elements: &a, index: index)
        }
    }
    func siftUp(elements: inout [Int], index: Int) {
        var index = index
        let v = elements[index]
        while index > 0 {
            let pindex = (index - 1) / 2
            let pv = elements[pindex]
            // 当前小于父节点，不用进行上滤了
            if v < pv {
                break
            }
            // 当前大于父节点
            elements[index] = pv
            index = pindex
        }
        elements[index] = v
    }
    
    func heapify2(a: inout [Int]) {
        // 如果从后想前处理，前面的元素可能需要下沉到后面；
        // 因为只需要从非叶子节点下滤就可以了
        for index in (0..<a.count/2).reversed() {
            siftDown(&a,length: a.count ,index: index)
        }
    }
    func siftDown(_ elements: inout [Int], length: Int, index: Int) {
        let v = elements[index]
        var index = index
        // 根节点从0开始
        while index < length / 2 {
            var childIndex = index * 2 + 1
            let rightIndex = childIndex + 1
            // 如果右子节点存在，且比左要打，上移的是右
            if rightIndex < length && elements[rightIndex] > elements[childIndex] {
                childIndex = rightIndex
            }
            // 如果最大的比当前的还小。则不用移动了
            if elements[childIndex] < v {
                break
            }
            elements[index] = elements[childIndex]
            index = childIndex
        }
        elements[index] = v
    }
    static func test(){
        let solution = BinaryHeapHeapify()
        var array = [30,34,73,60,68,43]
        solution.heapify2(a: &array)
        print(array)
    }
}
